/**
 * @file review.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2022-03-07
 *
 * @copyright Copyright (c) 2022
 *
 */

/**
 * 动态规划
 * 1. 基础问题
 *      斐波那契数列
 *      爬楼梯
 *      最小花费爬楼梯 dp[i]=min(dp[i-1],dp[i-2])+cost[i]
 *      不同路径
 *      343.整数拆分：将一个正整数n拆成k个数之和，使其乘积最大化
 *          要点：每个数都可以拆或不拆，枚举j （dp[i]=max(dp[i-j]*j, (i-j)*j, dp[i])）
 *      96.不同的BST树：恰由n个节点组成不同的BST树有多少种
 *          思路：枚举头结点求和，左子树dp[j-1]，右子树dp[i-j]
 *
 * 2. 背包问题
 * N个物品, 容量为W的背包，每个物品都有重量wt[i]和价值val[i]，最多能装的价值？
 *      “熟练写出一维dp“
 *      0-1 背包：每个物品只能选一次（一维内外循环不可换）
 *      for (int i = 0; i < N; ++i){
 *          for (int j = W; j >= wt[i]; --j){
 *              dp[j] = max(dp[j], dp[j - wt[i]] + val[i])
 *          }
 *      }
 *      分割等和子集
 *      目标和
 *      最后一块石头重量II
 *
 *      完全背包：每个物品可以选多次（一维内外循环可换）
 *      for (int i = 0; i < N; ++i){
 *          for (int j = wt[i]; j <= W; ++j){
 *              dp[j] = max(dp[j], dp[j - wt[i]] + val[i])
 *          }
 *      }
 *      零钱兑换II：凑成总金额的方法数。求组合（内外循环可换）
 *      组合总和IV：求排列（物品必须放置到内循环，以保证每次都从头开始取）
 *      零钱兑换：凑成总金额所需最少硬币数。
 *      完全平方数：和为N的完全平方数最少数量。和零钱兑换完全一致！
 *      单词拆分：是否可以利用字典中出现的单词拼凑出字符串s。
 *          dp[i]能否拆分取决于：前缀dp[j]能否拆分+剩余子串是否能在字典中找到
 *
 * 3. 打家劫舍：不触碰报警（相邻元素）能偷到的最大金额
 *      dp[i]--以nums[i]结尾能偷窃到的最大金额
 *      I.普通房子 dp[i]=max(dp[i-1], dp[i-2]+nums[i])
 *      II.房子围成了一圈 max([0,n-1], [1,n])
 *      III.二叉树构成的房子 dp[i][1]/dp[i][0] 表示该节点抢或不抢能得到的最大金额
 *          要点：该节点抢，那左右孩子就不能抢；若不抢，那就能抢一个孩子（取max）
 *
 * 4. 买卖股票：通过买卖股票获取最大利润
 *      dp非最优解，但却通用
 *      dp[i][0] 第i天持有股票所剩最大现金
 *          第i天持有=max(第i-1天持有，第i-1天不持有-第i天买入)
 *      dp[i][1] 第i天不持有股票所剩最大现金
 *          第i天不持有=max(第i-1天不持有，第i-1天持有+第i天卖出)
 *          return dp[n - 1][1]
 *      ...
 *      I.只能买卖各一次。贪心法：找最大间距（最小左值最大右值）
 *          如何保证只买一次（第i-1天不持有==0）
 *      II.买卖不限次数。贪心法：各种做T，有利润就卖
 *      III.至多完成两次买卖。
 *          dp[i][0]无操作，dp[i][1]第一次买入...dp[i][4]第二次卖出
 *      IV.至多完成K次买卖。
 *          dp[i][2*k]第K次卖出
 *      含手续费：不限次数买卖一次收取一次手续费。
 *          卖出时扣去手续费，返回时需要考虑（卖股票和不卖谁最大（手续费超过股价？啊这））
 *      含冷冻期：买卖一次后有个冷冻期1天。
 *
 * 5. 最**子序列
 *  300.最长递增子序列：返回最长严格递增子序列长度
 *      dp[i]=最长的(dp[j]+1) 枚举j 
 *  674.最长连续递增序列：返回最长连续递增子序列长度
 *      dp[i]=dp[i-1]+1 （如果连续递增，否则置为1）（这和贪心有啥区别？）
 *  718.最长重复子数组：返回两个数组AB的最长公共子数组长度
 *      dp[i][j]=dp[i-1][j-1]+1 ( if A[i-1]==B[j-1] )
 *  1143.最长公共子序列：返回两个字符串AB的最长公共子序列长度
 *      if (A[i-1]==B[j-1]){
 *          dp[i][j]=dp[i-1][j-1]+1;
 *      }else{
 *          dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
 *      }
 *  1035.不相交的线：实质就是同1143.
 *  53.最大子序和：返回具有最大和的连续子数组的和
 *      设dp[i]==包括到下标i之前的最大连续子序和
 *      dp[i]=max(dp[i-1]+nums[i],nums[i])
 *  
 * 6. 编辑距离
 *  dp[i][j]--s[0:i-1] t[0:j-1]
 *  # 不要忘记边界处理
 *  392.判断子序列：判断字符串s是否是字符串t的子序列
 *      思路：其实就是s是否可以通过插入操作得到t（这不就是乞丐版编辑距离么）
 *      思路二：双指针（若相等则一起++，否则t++）所以是简单题
 *  115.不同子序列：计算在字符串s的子序列中t出现的次数
 *      思路：其实s通过删除操作得到t的“方案数”
 *  49.两个字符串的删除操作：两个字符串通过删除操作得到一样的子串所需最小操作数
 *      思路：其实就是两个字符串都可以删除，最终相等所需”最小步数“
 *  72.编辑距离：将字符串s转成t的“最小编辑距离”
 *      思路：可以删除、插入、替换
 * 
 *  647.回文子串：求一个字符串中回文子串的数目
 *      dp[i][j]--[i:j]内的子串是否回文，用cnt计数
 *      if (s[i]==s[j]){
 *          if (j-i==1){    
 *              天然回文；
 *          }else if (取决于dp[i+1][j-1]) 那for循环i就得倒序呀
 *      }
 * 
 *  5.最长回文子串：返回最长回文子串
 *      思路：同上啊，记录最长的i，j
 *  516.最长回文子序列：返回最长回文子序列的长度
 *      dp[i][j]--[i:j]内最长回文子序列长度
 *      if (s[i]==s[j]){
 *          dp[i][j]=dp[i+1][j-1]+2;
 *      }else{ //说明s[i]和s[j]对回文子序列没有贡献，那么取其中最大值即可
 *          dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
 *      }
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    cout << '[';
    while (it != Containers.end()) {
        cout << *it << ", ";
        ++it;
    }
    cout << ']';
    cout << endl;
}

class GUPIAO
{
  public:
    int maxProfitI(vector<int> &prices)
    {
        // dp[i][0] 第i天持有股票所得最多现金
        // dp[i][1] 第i天不持有股票所得最多现金
        // 最后返回dp[n-1][1]
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; ++i) {
            // 持有有2种情况：前一天就持有，当天买入
            // 不持有也有2种情况：前一天就不持有，当天卖掉
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[n - 1][1];
    }

    int maxProfitI_2(vector<int> &prices)
    {
        int n = prices.size();
        int left = 10001;
        int len = -1;
        for (int i = 0; i < n; ++i) {
            left = min(left, prices[i]);
            len = max(len, prices[i] - left);
        }
        return len;
    }
    int maxProfitII(vector<int> &prices)
    {
        // dp[i][0] 第i天持有股票所得最多现金
        // dp[i][1] 第i天不持有股票所得最多现金
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; ++i) {
            // 持有有2种情况：前一天就持有，当天买入(前一天不持有+当天买入)
            // 不持有也有2种情况：前一天就不持有，当天卖掉
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[n - 1][1];
    }
    int maxProfitII_2(vector<int> &prices)
    {
        // 贪心：只要每天利润就买卖
        int n = prices.size();
        int res = 0;
        for (int i = 1; i < n; ++i) {
            res += max(prices[i] - prices[i - 1], 0);
        }
        return res;
    }
};

void testGUPIAO()
{
    GUPIAO solve = GUPIAO();
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << solve.maxProfitI(prices) << endl;
    cout << solve.maxProfitI_2(prices) << endl;
    cout << solve.maxProfitII(prices) << endl;
    cout << solve.maxProfitII_2(prices) << endl;
}

int main(int argc, const char **argv)
{
    testGUPIAO();
    return 0;
}